package algorithm.swordoff;

import algorithm.leetcode.ListNode;

/**
 * 链表中倒数第k个节点
 */

public class SQ22 {

    public ListNode getKthFromEnd(ListNode head, int k) {
        if (k == 0 || head == null) return head;

        ListNode fakeHead = new ListNode(-23121039);
        fakeHead.next = head;
        ListNode quick = fakeHead;
        ListNode slow = fakeHead;

        for (int i = k; i > 0; i--) {
            // 如果已经到链表末尾K还没到0(也就是说K比链表长度还长),就不操作直接返回
            if (quick == null) return head;
            else quick = quick.next;
        }

        while (quick.next != null) {
            quick = quick.next;
            slow = slow.next;
        }

        // 此时slow节点指向的是待删除的前面一个
        return slow.next;
    }

    /**
     * 未测试,断网那天写的.因为有可能会删掉头节点,所以需要设置一个虚空头节点
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode deleteLastKthNode(ListNode head, int k) {
        if (k == 0 || head == null) return head;

        ListNode fakeHead = new ListNode(-23121039);
        fakeHead.next = head;
        ListNode quick = fakeHead;
        ListNode slow = fakeHead;

        for (int i = k; i > 0; i--) {
            // 如果已经到链表末尾K还没到0(也就是说K比链表长度还长),就不操作直接返回
            if (quick == null) return head;
            else quick = quick.next;
        }

        while (quick.next != null) {
            quick = quick.next;
            slow = slow.next;
        }

        // 此时slow节点指向的是待删除的前面一个
        quick = slow.next.next;
        slow.next.next = null;
        slow.next = quick;

        return fakeHead.next;
    }


    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
//        ListNode f = new ListNode(6);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
//        e.next = f;
        SQ22 soe = new SQ22();
        System.out.println(soe.deleteLastKthNode(a, 0));

    }
}
